package com.zk.algorithm.backtracking;

import com.zk.algorithm.annotation.CrackingTheCodingInterview6;
import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.LeetCodeExplore;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zk
 */
@LeetCode
@LeetCodeExplore
@CrackingTheCodingInterview6("8.9")
public class GenerateParentheses {

    public static void main(String...args) {
        new GenerateParentheses().generateParenthesis(3);
    }

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    // 假设 n = 3
    //
    // 能够添加左括号的条件 open < 3: 0, 1, 2
    // 能够添加右括号的条件 close < open 右括号必须小于左括号
    public void backtrack(List<String> ans, String cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur + "(", open + 1, close, max);

        // ==============================
        // 这里不能写成 close <= open
        // 因为能够进入到这里的时候
        // open 已经 == max 了，即 open 是 3 了
        // 所以 close 的变化为 0 1 2
        // ==============================
        if (close < open)
            backtrack(ans, cur + ")", open, close + 1, max);
    }

}
